package study.数据结构.线性结构.递归;

public class MiGong {

    public static void main(String[] args) {
        //先创建一个二维数组模拟迷宫
        //地图
        int[][] map= new int[8][7];
        //使用1表示墙
        //先把上下全部置为1
        for (int i = 0; i < 7; i++) {
            map[0][i] = 1;
            map[7][i] = 1;
        }
        //左右全部置为1
        for (int i = 0; i < 8; i++) {
            map[i][0] = 1;
            map[i][6] = 1;
        }
        //设置挡板，1表示
        map[3][1] = 1;
        map[3][2] = 1;

        //输出地图
        System.out.println("地图的情况");
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[i].length; j++) {
                System.out.print(map[i][j]+" ");
            }
            System.out.println();
        }

        //使用递归回溯给小球找路
        setWay(map,1,1);
        System.out.println("小球探测过的地图");
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[i].length; j++) {
                System.out.print(map[i][j]+" ");
            }
            System.out.println();
        }

        //如何找到最短路径
        //思路：
        //1、因为不同的策略小球所走的路线是不同的，将所有的策略都写成方法
        //2、将策略方法执行后的map数组遍历，然后将其中的2放入一个集合中
        //3、最后比较各个策略对应的集合的长度， 最短的那个集合就是最短路径
    }

    //使用递归回溯来给小球找路
    //说明
    //1、map表示地图
    //2、i，j表示从地图的哪个位置开始出发（1，1）
    //3、如果小球能到map[6][5]位置，则说明通路找到
    //4、约定：当map[i][j]为0时表示该点没有走过   当为1时表示墙    当为2时表示通路  当为3时表示已经走过,是死路
    //5、在走迷宫时，需要确定一个策略（方法） 下-》右-》上-》左  因为不同的策略，小球走的路不一样
    //如果该点走不通，再回溯
    /**
     *
     * @param map 表示地图
     * @param i  从那个位置开始找 i是行
     * @param j  j是列
     * @return   如果找到通路就返回  true  否则返回false
     */
    public static boolean setWay(int[][] map,int i ,int j){
        if (map[6][5] == 2){  //通路已经找到
            return true;
        }else {
            if (map[i][j] ==0){  //如果当前这个点还没有走过
                //按照策略 下-》右-》上-》左走
                map[i][j] = 2; //假定该店可以走通
                if (setWay(map,i+1,j)){   //向下走
                    return true;
                }else if (setWay(map,i,j+1)){  //向右走
                    return true;
                }else if (setWay(map,i-1,j)){  //向上走
                    return true;
                }else if (setWay(map,i,j-1)){   //向左走
                    return true;
                }else {   //上下左右都走不通，是死路
                    map[i][j] = 3;
                    return false;
                }
            }else{  //如果map[i][j]!=0,可能是1，2，3
                return false;
            }
        }
    }
}
